﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.IsPalindromeLinkList
{
    class MainProject
    {
        static void Main(string[] args)
        {
            ListNode listNode1 = new ListNode(1);
            ListNode listNode2 = new ListNode(2);
            listNode1.next = listNode2;
            Console.WriteLine(IsPalindrome(listNode1));
            Console.ReadKey();
        }
        public static bool IsPalindrome(ListNode head)
        {
            Stack<ListNode> stack = new Stack<ListNode>();
            Queue<ListNode> queue = new Queue<ListNode>();
            ListNode listNode = head;
            while (listNode!=null)
            {
                stack.Push(listNode);
                queue.Enqueue(listNode);
                listNode = listNode.next;
            }
            while (queue.Count>0)
            {
                if (queue.Dequeue().val != stack.Pop().val)
                {
                    return false;
                }
            }
            return true;



            //超时了
            //string str = string.Empty;
            //ListNode linkList = head;
            //while (linkList!=null)
            //{
            //    str += linkList.val;
            //    linkList = linkList.next;
            //}
            //char[] first = str.ToArray();
            //char[] second = str.ToArray();
            //Array.Reverse(second);
            //string str1 = new string(first);
            //string str2 = new string(second);
            //return str1.Equals(str2);
        }
    }
}
